Air New Zealand được hình thành dưới tên gọi TEAL (Tasman Empire Airways Limited) vào năm 1940, thực hiện các dịch vụ bay trên chặng trans-Tasman. Sau chiến tranh thế giới thứ 2, TEAL khai thác các đường bay từ Auckland đi Sydney và Wellington đi Fiji với tần suất 1 chuyến 1 tuần. Chính phủ New Zealand và Australia đã mua 50% cổ phần của TEAL vào năm 1953 và hẵng đã ngừng các dịch vụ bay vào năm 1960. Với sự ra đời của máy bay DC-8 vào năm 1965, TEAL trở thành Air New Zealand, chính phủ New Zealand đã mua lại từ Australia 50% cổ phần của hẵng.

Cùng với sự phát triển của dòng máy bay DC-8s, Air New Zealand bắt đầu các dịch vụ vận chuyển của mình tới Mỹ và châu Á, năm 1965 hẵng bay tới Los Angeles và Honolulu. Sau đó hẵng đã đặt mua máy bay thân rộng DC-10. Năm 1981, hẵng bắt đầu đưa máy bay Boeing 747 vào khai thác. Năm 1982, Air New Zealand bắt đầu dịch vụ tới London, Vương quốc Anh.

Quốc hữu hóa

Tháng 10-2001, Air New Zealand được chính phủ New Zealand quốc hữu hoá trở lại với trong một kế hoạch trị giá 885 triệu đô la New Zealand (trong đó chính phủ chiếm 76.55 cổ phần) và sau đó có ban lãnh đạo mới. Động thái này đã đưa Air New Zealand tránh khỏi phá sản.Năm 2002, Air New Zealand phục hồi lại các dịch vụ bay quốc nội thông qua một kế hoạch hàng không giá rẻ, và chính phủ New Zealand đã cân nhắc (và sau đó từ chối) đề nghị của Qantas mua laị 1/5 cổ phần của hẵng. Air New Zealand có lãi trở lại vào năm 2003 với lợi nhuận sau thuế là 165.7 triệu đô la New Zealand và hẵng tiếp tục có lợi nhuận vào các năm sau.